//动态分配线程，解决链表访问问题，同时这部分也是能唯一并行化的地方
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<pthread.h>
#include<semaphore.h>
#include<sys/time.h>
using namespace std;

const int N = 10000, M = N*N;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
typedef pair<int, int> PII;
int st[N], dist[N];
priority_queue<PII, vector<PII>, greater<PII> >heap;

int NUM_THREADS = 7;
sem_t sem_available;
pthread_mutex_t mutex;
typedef struct {
	int indexOfEdge;
	int selectedNode;
}threadParam;
void* threadFunc(void* param) {
	threadParam* p = (threadParam*)param;
	int index = p->indexOfEdge;
	int v = p->selectedNode;
	int j = e[index];
	if (dist[j] > dist[v] + w[index]) {
		dist[j] = dist[v] + w[index];
		pthread_mutex_lock(&mutex);
		heap.push({ dist[j],j });
		pthread_mutex_unlock(&mutex);
	}
	sem_post(&sem_available);
	pthread_exit(NULL);
	
	return NULL;
}


int main(int argc,char** args) {
	memset(dist, 0x3f, sizeof dist);
	memset(h, -1, sizeof h);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		scanf("%d%d%d",&a,&b,&c);
		add(a, b, c);
	}
	dist[1] = 0;
	heap.push({ 0,1 });


	pthread_mutex_init(&mutex, NULL);
	sem_init(&sem_available, 0, NUM_THREADS);


	NUM_THREADS=args[1][0]-'0';
    struct timeval t1,t2;
    double time=0.0;
	gettimeofday(&t1,NULL);
	////
	while (!heap.empty()) {
		auto head = heap.top();
		heap.pop();
		int v = head.second, d = head.first;
		if (st[v])continue;
		st[v] = 1;
		for (int i = h[v]; ~i; i = ne[i]) {
			threadParam* param=new threadParam;
			param->indexOfEdge = i;
			param->selectedNode = v;
			sem_wait(&sem_available);
			pthread_t* handle=new pthread_t;
			pthread_create(handle, NULL, threadFunc, param);
		}
		for (int i = 0; i < NUM_THREADS; ++i)
			sem_wait(&sem_available);
		for (int i = 0; i < NUM_THREADS; ++i)
			sem_post(&sem_available);//一定要记得恢复信号量啊，否则下一步卡死了
	}

	////
	gettimeofday(&t2,NULL);
	time=(double)(t2.tv_sec-t1.tv_sec)*1000.0 + (double)(t2.tv_usec-t1.tv_usec)/1000.0;
	cout<< time;
}